#include<stdio.h>
#include "test.h"
#include <stdlib.h>
#include <string.h>


/*  // 一般标准写法
void shell_sort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {       // 增量逐步缩小
        for (int i = gap; i < n; i++) {            // 遍历子序列
            int temp = arr[i];                     // 待插入元素
            int j;
            for (j = i; j >= gap && arr[j-gap] > temp; j -= gap) {
                arr[j] = arr[j-gap];               // 大元素后移
            }
            arr[j] = temp;                         // 插入正确位置
        }
    }
}
    */




void shell_sort_up(int arr[], int n){
    int gap = 0;
    int i = 0;
    for(gap=n/2;gap>0;gap=gap/2){    //慢慢减小gap ,让子序列越来越大，直到等于整个数组大小（gap =1)
        for(i=0;i<gap;i++){          // 一次循环处理一个序列

            for(int j=i+gap;j<n;j=j+gap){      // j 是要插入的值。 [i,gap+i,i+gap+gap,i+gap+gap+gap,......]
                int temp = arr[j];
                int k = j-gap;                  // k 比较的值。
                while(k>=i && arr[k]>temp){
                    arr[k+gap] = arr[k];
                    k = k - gap;
                }
                arr[k+gap] = temp;
                
            }

        }
    }
}

void shell_sort_up_v2(int arr[], int n){
    int gap =0;
    int i = 0;
    int j = 0;
    int temp = 0;

    for(gap=n/2;gap>0;gap=gap/2){   // 减小gap ,增大 子序列长度，直到gap= 1
        i = gap;
        for(;i<n;i++){              // 一个循环处理所有子序列，只要移动关系对应上就正确了。
            temp = arr[i];
            j = i-gap;                    //i 所在序列往左对应的第一个序列。
            while(j>=0 && (arr[j]>temp)){        // i 先和第一个比较
                arr[j+gap] = arr[j];             // 移动。
                j = j - gap;                     // 往左找
            }
            arr[j+gap] = temp;                     // 插入
        }

    }

}

int main() {
    int arr[] = {5, 4, 3, 2, 1,-4,45,-0,56};
    int n = sizeof(arr) / sizeof(arr[0]);  // 计算数组长度
    
    shell_sort_up_v2(arr, n);  // 调用排序函数
   // bubble_sort_down(arr, n);
    
    // 打印排序结果
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }

  //  benchmark(shell_sort_up);
    benchmark(shell_sort_up_v2);

    return 0;
}